package lk;

import lk.D231001.TreeNode;

import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class D231004 {
    // 删除二叉搜索树中的节点
    // 时间：O(n)
    // 空间：O(1)
    public TreeNode deleteNode(TreeNode root, int key) {
        TreeNode cur = root;
        TreeNode parent = null;

        // 寻找待删除节点, 同时记录下待删除节点的父节点
        while (cur != null && cur.val != key) {
            parent = cur;
            if (cur.val > key) {
                cur = cur.left;
            } else {
                cur = cur.right;
            }
        }


        if (cur == null) {
            // 没找到待删除节点
            return root;
        }

        if (cur.left == null && cur.right == null) {
            // 1. 待删除节点是叶子节点, 直接删除
            cur = null;
        } else if (cur.left == null) {
            // 2. 待删除结点左边为空, 右子树与父节点对接
            cur = cur.right;
        } else if (cur.right == null) {
            // 3. 待删除结点右边为空, 左子树与父节点对接
            cur = cur.left;
        } else {
            // 4. 待删除结点左右都不空
            // 在右子树中, 一直向左找, 找到右子树中的最小值(叶子节点)
            TreeNode tmp = cur.right;
            TreeNode tmpParent = cur;
            while (tmp.left != null) {
                tmpParent = tmp;
                tmp = tmp.left;
            }
            // 将这个最小节点, 从原本位置上移除
            if (tmpParent.val == cur.val) {
                tmpParent.right = tmp.right;
            } else {
                tmpParent.left = tmp.right;
            }
            // 取代待删除节点的位置
            tmp.right = cur.right;
            tmp.left = cur.left;
            cur = tmp;
        }

        if (parent == null) {
            return cur;
        } else {
            if (parent.left != null && parent.left.val == key) {
                parent.left = cur;
            } else {
                parent.right = cur;
            }
            return root;
        }
    }


    // 钥匙和房间
    // 广度优先搜索
    // 时间：O(n + m)
    // 空间：O(n)
    public boolean canVisitAllRooms(List<List<Integer>> rooms) {
        // n - 总房间数, num - 进入的房间数量
        int n = rooms.size(), num = 0;
        // 用来记录是否拿到过第 i 号房间的钥匙
        boolean[] vis = new boolean[n];
        // 存储拿到的钥匙
        Queue<Integer> que = new LinkedList<Integer>();
        // 拿到 0 号房间的钥匙
        vis[0] = true;
        que.offer(0);
        while (!que.isEmpty()) {
            // 从队列中获取钥匙
            int x = que.poll();
            // 进入的房间数 +1
            num++;
            for (int it : rooms.get(x)) {
                // 遍历整个房间内的钥匙
                if (!vis[it]) {
                    // 如果没有拿到过, 就加入队列
                    vis[it] = true;
                    que.offer(it);
                }
            }
        }
        return num == n;
    }



    // 省份数量
    // 时间：O(n ^ 2)
    // 空间：O(n)
    public int findCircleNum(int[][] isConnected) {
        // 城市数量
        int cities = isConnected.length;
        // 是否访问过
        boolean[] visited = new boolean[cities];
        // 省份数量
        int provinces = 0;
        // 队列, 存储 待访问的城市
        Queue<Integer> queue = new LinkedList<Integer>();

        // 遍历数组访问每一个城市
        for (int i = 0; i < cities; i++) {

            // 如果当前城市没有被访问过
            if (!visited[i]) {

                queue.offer(i);
                // 访问与当前城市连通的所有城市
                while (!queue.isEmpty()) {
                    int j = queue.poll();
                    visited[j] = true;
                    for (int k = 0; k < cities; k++) {
                        if (isConnected[j][k] == 1 && !visited[k]) {
                            queue.offer(k);
                        }
                    }
                }

                // 省份数量 + 1
                provinces++;
            }
        }
        return provinces;
    }
}
